//二叉树的三种深度优先遍历方式：前序遍历，中序遍历，后序遍历，其中的序指的是根结点的遍历顺序，三种遍历方式都是先左后右


#include <vector>
using std::vector;
struct TreeNode
{
    int val;
    TreeNode* leftchild;
    TreeNode* rightchild;
    TreeNode():val(0),leftchild(nullptr),rightchild(nullptr){}
    TreeNode(int x):val(x),leftchild(nullptr),rightchild(nullptr){}
    TreeNode(int x,TreeNode* lc,TreeNode* rc):val(x),leftchild(lc),rightchild(rc){}
};
//第一种是递归的写法、

//前序遍历
void pretraversal(TreeNode* cur,vector<int>& res)
{
    if(cur==nullptr) return; //cur到叶子结点下一个，结束函数

    res.push_back(cur->val);    //前序：先取中结点数据
    pretraversal(cur->leftchild,res);
    pretraversal(cur->rightchild,res);
}

vector<int> PreorderTraversal(TreeNode* root)
{
    vector<int> ans;
    pretraversal(root,ans);
    return ans;
}


//中序遍历
void intraversal(TreeNode* cur,vector<int>& res)
{
    if(cur==nullptr) return; //cur到叶子结点下一个，结束函数

    intraversal(cur->leftchild,res);
    res.push_back(cur->val);    //中序：先遍历左子树再取中结点数据
    intraversal(cur->rightchild,res);
}

vector<int> InorderTraversal(TreeNode* root)
{
    vector<int> ans;
    intraversal(root,ans);
    return ans;
}

//后序遍历
void posttraversal(TreeNode* cur,vector<int>& res)
{
    if(cur==nullptr) return; //cur到叶子结点下一个，结束函数

    posttraversal(cur->leftchild,res);
    posttraversal(cur->rightchild,res);
    res.push_back(cur->val);    //后序：先遍历左右子树再取中结点数据
}

vector<int> PreorderTraversal(TreeNode* root)
{
    vector<int> ans;
    posttraversal(root,ans);
    return ans;
}

//不难发现，三种遍历方式的不同只有在traversal函数中：读取根节点的顺序不同而已，这也是递归方法导致的简洁代码